This invention relates to pattern detection methods and systems, and, more particularly, to face detection methods and systems.
In recent years, problems associated with general visual pattern recognition or object recognition/classification have received an increasing amount of attention in the computer vision community. In many cases the only feasible approach is to represent a class of patterns/objects (e.g. faces) by a set of learned examples. The complexity of some of the class of objects/patterns is often such that an extremely large set of examples is needed in order to learn all the potential variations (facial expression/pose etc). Additionally, typically the data points associated with the examples belong to some high-dimensional space. Thus, there has been and continues to be a need for pattern recognition techniques that can handle large data sets in high dimensional spaces.
One particular type of visual pattern is a face. Typically, face detection represents a very computationally intensive task that involves testing a digitized image for the location of a face by placing an observation window at all scales, in all positions, and at all orientations on the image, and ascertaining whether a face is present within the observation window. This process, however, can be quite slow. Exemplary face detection techniques are described in the following references, to which the reader is referred for additional material: Osuna et al., Training support vector machines: An application to face detection, Proc. Computer Vision and Pattern Recognition ""97, pages 130-136, 1997; and Rowley et al., Neural network-based face detection, Proc. IEEE Conf. On Computer Vision and Pattern Recognition, pages 203-207, IEEE, 1996.
Nonlinear Support Vector Machines (SVMs) are known to lead to excellent classification accuracies on a wide range of tasks, including face detection. The following references describe non-linear SVMs and their various characteristics: Schxc3x6lkopf et al., Advances in Kernel Methodsxe2x80x94Support Vector Learning, MIT Press, Cambridge, Mass., 1999; and Vapnik, The Nature of Statistical Learning Theory Statistical Learning Theory, Springer, N.Y. 1995.
Nonlinear SVMs are, however, usually slower classifiers than neural networks. The reason for this is that their run-time complexity is proportional to the number of support vectors (SVs), i.e. to the number of training examples that the SVM algorithm utilizes in the expansion of the decision function. While it is possible to construct classification problems, even in high-dimensional spaces, where the decision surface can be described by two SVs only, it is normally the case that the set of SVs forms a substantial subset of the whole training set.
There has been a fair amount of research on methods for reducing the run-time complexity of SVMs. Exemplary articles includes the following: Burges, Simplified support vector decision rules, Proceedings, 13th Intl. Conf. On Machine Learning, pages 71-77, San Mateo, Calif., 1996; and Schxc3x6lkopf et al., Input space vs. feature space in kernel-based methods, IEEE Transactions on Neural Networks, 10(5):1000-1017, 1999. Yet, the run time complexity of SVMs continues to be an issue in their efficient employment for pattern recognition or classification.
Accordingly, this invention arose out of concerns associated with improving the systems and methods that are utilized for pattern recognition or classification. Particular concerns giving rise to the invention were those associated with improving the efficiencies with which the evaluation of support vector expansions is utilized for pattern classification, particularly where the patterns comprise faces.
Systems and methods for object or pattern detection that use a nonlinear support vector (SV) machine are described. In the illustrated and described embodiment, objects or patterns comprising faces are detected. The decision surface (in the high dimensional data space) is approximated in terms of a reduced set of expansion vectors. In order to determine the presence of a face, the kernelized inner products of the reduced set vectors with the input pattern are sequentially evaluated and summed, such that if at any point the pattern can be rejected as not comprising a face, no more reduced set vectors are used. The sequential application of the reduced set vectors produces a substantial saving in computational time.